package com.maltys.dp.backpack;

/**
 * @author malty
 */
public class BestTimeToBuyAndSellStock {
    public static void main(String[] args) {
        BestTimeToBuyAndSellStock sellStock = new BestTimeToBuyAndSellStock();
//        int maxProfit = sellStock.maxProfit(new int[]{7,6,4,3,1});
//        int maxProfit = sellStock.maxProfit2(new int[]{7, 1, 5, 3, 6, 4});
        int maxProfit = sellStock.maxProfit3(new int[]{2, 4, 1});
        System.out.println(maxProfit);
        int maxProfit2 = sellStock.maxProfit4(2, new int[]{2, 4, 1});
        System.out.println(maxProfit2);
    }

    /**
     * dp[i][0] 第i天持有
     * dp[i][1] 第i天不持有
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return Math.max(dp[dp.length - 1][0], dp[dp.length - 1][1]);
    }

    public int maxProfit2(int[] prices) {
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            sum += Math.max(prices[i] - prices[i - 1], 0);
        }
        return sum;
    }

    /**
     * dp[i][0]  未操作
     * dp[i][1]  第一次持有
     * dp[i][2]  第一次不持有
     * dp[i][3]  第二次持有
     * dp[i][4]  第二次不持有
     *
     * @return
     */
    public int maxProfit3(int[] prices) {
        int[][] dp = new int[prices.length][5];
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[dp.length - 1][4];
    }

    public int maxProfit4(int k, int[] prices) {
        int[][] dp = new int[prices.length][2 * k + 1];
        for (int i = 1; i <= k << 1; i += 2) {
            dp[0][i] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = dp[i - 1][0];
            for (int j = 1; j <= k << 1; j++) {
                int val = j % 2 == 1 ? -prices[i] : prices[i];
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + val);
            }
        }
        return dp[dp.length - 1][k << 1];
    }
}
